package com.kevin.Code.Heap;

import java.util.PriorityQueue;

/**
 * @author Vinlee Xiao
 * @Classname KthLargestElementinanArray
 * @Description Leetcode 215. 数组中的第K个最大元素 中等难度 堆 二刷 字节面试题
 * @Date 2022/2/28 10:23
 * @Version 1.0
 */
public class KthLargestElementinanArray {


    /**
     * 通过快速排序 实现寻找第K大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest1(int[] nums, int k) {
        return sortArray(nums, k);
    }


    /**
     * 通过归并排序，实现寻找第K个大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest2(int[] nums, int k) {
        mergeSortArray(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    /**
     * 通过堆排序，实现寻找第K个大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest3(int[] nums, int k) {

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int num : nums) {
            priorityQueue.add(num);
        }

        for (int i = 0; i < nums.length - k - 1; i++) {
            priorityQueue.poll();
        }
        return priorityQueue.peek();

    }


    /**
     * @param nums
     * @param k
     * @return
     */
    public int sortArray(int[] nums, int k) {
        int i = quickSort(nums, k, 0, nums.length - 1);
        if (i == Integer.MAX_VALUE) {
            return nums[nums.length - k];
        }
        return i;
    }

    /**
     * 手写快速排序
     *
     * @param nums
     * @param k
     * @return
     */
    private int quickSort(int[] nums, int k, int low, int high) {

        if (high <= low) {
            return Integer.MAX_VALUE;
        }

        int pviot = nums[low];
        int i = low;
        int j = high;

        while (i < j) {

            while (i < j && pviot <= nums[j]) {
                j--;
            }

            while (i < j && pviot >= nums[i]) {
                i++;
            }

            if (i < j) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
            }
        }
        nums[low] = nums[j];
        nums[j] = pviot;

        if (nums.length - j == k) {
            return nums[j];
        }
        int left = quickSort(nums, k, low, j - 1);
        int right = quickSort(nums, k, j + 1, high);

        if (left != Integer.MAX_VALUE) {
            return left;
        } else {
            return right;
        }
    }

    /**
     * @param nums
     * @param low
     * @param high
     * @return
     */
    private void mergeSortArray(int[] nums, int low, int high) {

        if (low < high) {
            int mid = (low + high) >> 1;
            mergeSortArray(nums, low, mid);
            mergeSortArray(nums, mid + 1, high);
            merge(nums, low, high, mid);
        }
    }

    /**
     * }
     * 合并排序
     *
     * @param nums
     * @param low
     * @param high
     */
    private void merge(int[] nums, int low, int high, int mid) {
        //建立临时数组，用于储存最终的结果
        int[] tmp = new int[high - low + 1];
        //用于记录下标
        int cnt = 0;
        int i = low;
        int j = mid + 1;

        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                tmp[cnt] = nums[i];
                i++;
            } else {
                tmp[cnt] = nums[j];
                j++;
            }
            cnt++;
        }

        while (i <= mid) {
            tmp[cnt++] = nums[i++];
        }

        while (j <= high) {
            tmp[cnt++] = nums[j++];
        }

        if (cnt >= 0) {
            System.arraycopy(tmp, 0, nums, low, cnt);
        }

    }

    public static void main(String[] args) {
        KthLargestElementinanArray kthLargestElementinanArray = new KthLargestElementinanArray();
        int[] nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int i = kthLargestElementinanArray.findKthLargest2(nums, 4);
        System.out.println(i);

    }
}
